'''
Created on 15/10/2013

@author: daniel
'''
import colecciones.listaEnlazada
import ej1DefinicionDeGrafo.grafo
import ej1DefinicionDeGrafo.vertice
import ej2RecorridosDFSyBFS.recorridos
import unittest


class ResolvedorDeLaberinto(ej2RecorridosDFSyBFS.recorridos.Recorridos):

    def minimoDeEncrucijadas(self,grafo,origen,destino):
        if(origen.__cmp__(destino)==0):return 0
        nroDeAristas=0
        if nroDeAristas>grafo.getListaDeVertices().getTamanio(): return None
        if not grafo.getListaDeVertices().incluye(destino): return None
        
        lista=self.verticesADistanciaConBFS(grafo, origen, nroDeAristas)
        while not lista.incluye(destino):
            
            lista=self.verticesADistanciaConBFS(grafo, origen, nroDeAristas)
            if not lista.incluye(destino):nroDeAristas+=1
            
        return nroDeAristas
    
class Test(unittest.TestCase):


    def testName(self):
        self.assertIsInstance(ResolvedorDeLaberinto(),ResolvedorDeLaberinto,"Verifica correcta creacion")
        
    def testMinimoDeEncrucijadas(self):
        grafo=ej1DefinicionDeGrafo.grafo.Grafo()
        grafo.agregarVertice(
                 ej1DefinicionDeGrafo.vertice.Vertice(1,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                            )
        grafo.agregarVertice(
                 ej1DefinicionDeGrafo.vertice.Vertice(2,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 ej1DefinicionDeGrafo.vertice.Vertice(3,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 ej1DefinicionDeGrafo.vertice.Vertice(4,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 ej1DefinicionDeGrafo.vertice.Vertice(5,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 ej1DefinicionDeGrafo.vertice.Vertice(6,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 ej1DefinicionDeGrafo.vertice.Vertice(7,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.conectar(grafo.vertice(0), grafo.vertice(3), 0)# 1 con 4
        grafo.conectar(grafo.vertice(0), grafo.vertice(1), 0)# 1 con 2
        grafo.conectar(grafo.vertice(1), grafo.vertice(4), 0)# 2 con 5
        grafo.conectar(grafo.vertice(2), grafo.vertice(4), 0)# 3 con 5
        grafo.conectar(grafo.vertice(3), grafo.vertice(5), 0)# 4 con 6
        grafo.conectar(grafo.vertice(3), grafo.vertice(1), 0)# 4 con 2
        grafo.conectar(grafo.vertice(3), grafo.vertice(2), 0)# 4 con 3
        grafo.conectar(grafo.vertice(3), grafo.vertice(4), 0)# 4 con 5
        grafo.conectar(grafo.vertice(4), grafo.vertice(6), 0)# 5 con 7
        grafo.conectar(grafo.vertice(5), grafo.vertice(6), 0)# 6 con 7
        grafo.conectar(grafo.vertice(5), grafo.vertice(2), 0)# 6 con 3
        res=ResolvedorDeLaberinto()
#         print res.minimoDeEncrucijadas(grafo,grafo.vertice(0),grafo.vertice(6))
        self.assertEquals(res.minimoDeEncrucijadas(grafo,grafo.vertice(0),grafo.vertice(1)),1,"verifica minimo camino")
        self.assertEquals(res.minimoDeEncrucijadas(grafo,grafo.vertice(0),grafo.vertice(2)),2,"verifica minimo camino")
        self.assertEquals(res.minimoDeEncrucijadas(grafo,grafo.vertice(0),grafo.vertice(3)),1,"verifica minimo camino")
        self.assertEquals(res.minimoDeEncrucijadas(grafo,grafo.vertice(0),grafo.vertice(4)),2,"verifica minimo camino")
        self.assertEquals(res.minimoDeEncrucijadas(grafo,grafo.vertice(0),grafo.vertice(5)),2,"verifica minimo camino")
        self.assertEquals(res.minimoDeEncrucijadas(grafo,grafo.vertice(6),grafo.vertice(6)),0,"verifica minimo camino")
        self.assertEquals(res.minimoDeEncrucijadas(grafo,grafo.vertice(5),grafo.vertice(6)),1,"verifica minimo camino")
        self.assertEquals(res.minimoDeEncrucijadas(grafo,grafo.vertice(0),grafo.vertice(6)),3,"verifica minimo camino")


if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testName']
    unittest.main()